#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* x,int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//void InsertSort(int* a, int n)
//{
//
//	for (int  i = 0; i < n-1; i++)
//	{
//		int end = i;
//		int tmp = end+1;
//		while (end >= 0)
//		{
//			if (a[end] > a[tmp])
//			{
//				Swap(&(a[end]), &(a[tmp]));
//			}
//			else
//			{
//				end--;
//				tmp--;
//				continue;
//			}
//			end--;
//			tmp--;
//		}
//	}
//}

void InsertSort(int* a, int size)
{
	for (int i = 0; i < size-1; i++)
	{
		//单趟排序
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
			}
			else
			{
				break;
			}
			end--;
		}
		a[end + 1] = tmp;
	}
}
int main()
{
	int a[] = { 2,5,4,7,9,3,6,1 };
	InsertSort(a, 8);
	for (int  i = 0; i < 8; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}